#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include "BinaryTree.h"
#include <iostream>
#include <iostream>
using std::ostream;
using std::istream;
#include <functional>
using std::pair;
using std::make_pair;
using std::less;
#include <new> 
#define BST( Key, T ) BinarySearchTree<Key, T>
template<typename Key, typename T, typename comp = less<Key> >
class BinarySearchTree : protected BinaryTree< pair<Key, T> >
{
	/*template<typename Key, typename T, typename comp> friend ostream & operator <<(
				ostream &out,const BinarySearchTree &r);*/
	/*template<typename Key, typename T, typename comp> friend istream & operator >>(
				istream &in, BinarySearchTree &r);*/
public:
        typedef typename BinaryTree< pair<Key,T> >::TreeNode TreeNode;
	//constructors
	BinarySearchTree();
	BinarySearchTree(const BinarySearchTree& tree)
		throw(TreeException);

	//operations
	virtual T* find( const Key& key );
	virtual const T* find( const Key& key ) const;
	virtual T& operator[](const Key &index);
	virtual void Insert(const Key& key, const T &item)
      throw(TreeException);
	virtual void Delete(const Key &key)
      throw(TreeException);
	virtual void Delete(const Key& key, T &out)
      throw(TreeException);
	virtual const T& Retrieve(const Key& key)const 
		throw(TreeException);
	virtual T& Retrieve(const Key& key) 
		throw(TreeException);
	virtual BinarySearchTree& operator=(BinarySearchTree& rhs) 
		throw(TreeException);
	//Traversals
	virtual void preorderTraverse( void (*visit)(pair<Key,T> &anItem)) const;
	virtual void inorderTraverse( void (*visit)(pair<Key,T> &anItem)) const;
	virtual void postorderTraverse( void (*visit)(pair<Key,T> &anItem)) const;
	virtual size_t size() const;
	virtual bool empty() const { return _size == 0; }
        virtual void clear() { this->destroyTree(this->rootPtr()); 
           this->setRootPtr(NULL); _size = 0;  }
	
protected:
	size_t _size;
	comp compare;
	//utility functions
	static void PrintItem(pair<Key,T> &item);
	void insertItem(TreeNode ** treePtr, const pair<Key,T>& newItem) 
		throw(TreeException);
	void deleteItem(TreeNode ** treePtr, const Key &item) 
		throw(TreeException);
	void deleteItem(TreeNode ** treePtr, const Key &item, T &out) 
		throw(TreeException);
	void deleteNodeItem(TreeNode ** nodePtr);
	void processLeftmost(TreeNode ** nodePtr, pair<Key,T>& treeItem);
	const T& retrieveItem(TreeNode *treePtr, const Key &searchKey) const throw(TreeException);
	T& retrieveItem(TreeNode *treePtr, const Key &searchKey) throw(TreeException);

};


//**********************************
//*		Default Constructor
//**********************************
template<typename Key, typename T, typename comp>
BinarySearchTree<Key, T, comp>::BinarySearchTree() 
{
   _size = 0;
   compare = comp();
}
//**********************************
//*		Copy Constructor
//**********************************
template<typename Key, typename T, typename comp>
BinarySearchTree<Key, T, comp>::BinarySearchTree(const BinarySearchTree& tree) throw(TreeException)
{
   _size = tree._size;
   compare = comp();
   copyTree(tree.rootPtr(),this->rootPtr());
}

//**********************************
//*		size
//**********************************
template<typename Key, typename T, typename comp>
size_t BinarySearchTree<Key, T, comp>::size() const {
	return _size;
}
//**********************************
//*		Insert
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::Insert(const Key& key, const T &item)
   throw(TreeException)
{
	
	insertItem(this->rootPtr(), make_pair(key,item) );
} 
//**********************************
//*		Insert Item
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::insertItem(TreeNode **treePtr,
				  const pair<Key,T>& newItem)
   throw(TreeException)
{

	TreeNode **ptr = treePtr;
	while ( *ptr  != NULL ) {
		if( newItem.first == (*ptr)->item.first ) { //unique check
			(*ptr)->item.second = newItem.second;
			return;
		}
		if( compare(newItem.first, (*ptr)->item.first ) ) {
			ptr = &(*ptr)->leftChildPtr;
		}
		else {
			ptr = &(*ptr)->rightChildPtr;
		}
	}
	_size++;
	*ptr = new TreeNode( newItem,NULL,NULL );

}  // end insertItem

//**********************************
//*		Delete
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::Delete(const Key& key, T &out)
      throw(TreeException)
{
	deleteItem(this->rootPtr(), key, out);
}
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::Delete(const Key &key)
      throw(TreeException)
{
	deleteItem(this->rootPtr(),key);
}
//**********************************
//*		Delete Item
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::deleteItem(TreeNode ** treePtr,
												const Key &key, T &out) 
		throw(TreeException)
{
TreeNode** ptr = treePtr;
	while( *ptr != NULL ) {
		if( key == (*ptr)->item.first ){
			out = (*ptr)->item.second;
			deleteNodeItem(ptr);  // delete the item
			--_size;
			return;
		}
		else if ( compare(key, (*ptr)->item.first) ) {
			ptr = & (*ptr)->leftChildPtr;
		}
		else {
			ptr = & (*ptr)->rightChildPtr;
		}

	}
	throw TreeException("TreeException: delete failed");  // empty tree
}
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::deleteItem(TreeNode ** treePtr, 
													const Key &key) 
		throw(TreeException)
{
	TreeNode** ptr = treePtr;
	while( *ptr != NULL ) {
		if( key == (*ptr)->item.first ){
			deleteNodeItem(ptr);  // delete the item
			--_size;
			return;
		}
		else if ( compare(key, (*ptr)->item.first) ) {
			ptr = & (*ptr)->leftChildPtr;
		}
		else {
			ptr = & (*ptr)->rightChildPtr;
		}

	}
	throw TreeException("TreeException: delete failed");  // empty tree
}
//**********************************
//*		Delete Node Item
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::deleteNodeItem(TreeNode ** nodePtr)

{
   TreeNode     *delPtr;
   pair<Key,T> replacementItem;

   // test for a leaf
   if ( ((*nodePtr)->leftChildPtr == NULL) &&
        ((*nodePtr)->rightChildPtr == NULL) )
   {  
      delete *nodePtr;
      *nodePtr = NULL;
   }  // end if leaf
   // test for no left child
   else if ((*nodePtr)->leftChildPtr == NULL)
   {  
      delPtr = *nodePtr;
      *nodePtr = (*nodePtr)->rightChildPtr;
      delPtr->rightChildPtr = NULL;
      delete delPtr;
   }  // end if no left child

   // test for no right child
   else if ((*nodePtr)->rightChildPtr == NULL)
   {  
      delPtr = *nodePtr;
      *nodePtr = (*nodePtr)->leftChildPtr;
      delPtr->leftChildPtr = NULL;
      delete delPtr;
   }  // end if no right child

   // there are two children:
   // retrieve and delete the inorder successor
   else
   {  
      processLeftmost(&(*nodePtr)->rightChildPtr, replacementItem);
      (*nodePtr)->item = replacementItem;
   }  // end if two children
}  
//**********************************
//*		Process Leftmost
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::processLeftmost(TreeNode ** nodePtr, 
      pair<Key,T>& treeItem)
{
   TreeNode *delPtr = *nodePtr;
   TreeNode ** ptr = nodePtr;

   while( (*ptr)->leftChildPtr != NULL ) {
      ptr = & (*ptr)->leftChildPtr;
   }
   treeItem = (*nodePtr)->item;
   nodePtr = &(*nodePtr)->rightChildPtr;
   delPtr->rightChildPtr = NULL;  // defense
   delete delPtr;

}
//**********************************
//*		Assignment Operator ( = )
//**********************************
template<typename Key, typename T, typename comp>
BinarySearchTree<Key, T, comp>& BinarySearchTree<Key, T, comp>::operator=(
      BinarySearchTree& rhs) 
throw(TreeException)
{
   if(this == &rhs)
      return *this;
   else {
      copyTree(*rhs.rootPtr(),this->rootPtr());
      return *this;
   }
}
//**********************************
//*		Pre Order Traverse
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::preorderTraverse( 
      void (*visit)(pair<Key,T> &anItem)) const
{
   this->preorder(this->rootPtr(),visit);
}
//**********************************
//*		In Order Traverse
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::inorderTraverse( 
      void (*visit)(pair<Key,T> &anItem)) const
{
   this->inorder(this->rootPtr(),visit);
}
//**********************************
//*		Post Order Traverse
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::postorderTraverse( 
      void (*visit)(pair<Key,T> &anItem)) const
{
   this->postorder(this->rootPtr(),visit);
}
//**********************************
//*		PrintItem
//**********************************
template<typename Key, typename T, typename comp>
void BinarySearchTree<Key, T, comp>::PrintItem(pair<Key,T> &item)
{
   std::cout << item.first << ": "<< item.second << std::endl;
}
//**********************************
//*		Stream Insertion Operator
//**********************************
template<typename Key, typename T, typename comp>
ostream & operator <<(ostream &out,const BinarySearchTree<Key, T, comp> &r)
{
   if(!r.isEmpty())
      r.inorderTraverse(BinarySearchTree<Key, T, comp>::PrintItem);
   else
      out << "Tree is empty";
   return out;
}
//**********************************
//*		Retrieve
//**********************************
template<typename Key, typename T, typename comp>
const T& BinarySearchTree<Key, T, comp>::Retrieve(const Key& key)const  throw(TreeException)
{
   return retrieveItem(this->rootPtr(), key);
}
template<typename Key, typename T, typename comp>
T& BinarySearchTree<Key, T, comp>::Retrieve(const Key& key)  throw(TreeException)
{
   return retrieveItem(*(this->rootPtr()), key);
}
//**********************************
//*		retrieveItem
//**********************************
template<typename Key, typename T, typename comp>
const T& BinarySearchTree<Key, T, comp>::retrieveItem(TreeNode *treePtr,
      const Key &searchKey) const
throw(TreeException)
{
   while (treePtr != NULL) {
      if (searchKey == treePtr->item.first)
         // item is in the root of some subtree
         return treePtr->item.second;

      else if ( compare(searchKey, treePtr->item.first))
         // search the left subtree
         treePtr = treePtr->leftChildPtr;

      else  // search the right subtree
         treePtr = treePtr->rightChildPtr;
   }
   throw TreeException("TreeException: searchKey not found");
} 
template<typename Key, typename T, typename comp>
T& BinarySearchTree<Key, T, comp>::retrieveItem(TreeNode *treePtr,
      const Key &searchKey) 
throw(TreeException)
{
   while (treePtr != NULL) {
      if (searchKey == treePtr->item.first)
         // item is in the root of some subtree
         return treePtr->item.second;

      else if ( compare(searchKey, treePtr->item.first))
         // search the left subtree
         treePtr = treePtr->leftChildPtr;

      else  // search the right subtree
         treePtr = treePtr->rightChildPtr;
   }
   throw TreeException("TreeException: searchKey not found");
}
//**********************************
//*		find
//**********************************
template<typename Key, typename T, typename comp>
T* BinarySearchTree<Key, T, comp>::find( const Key& key ) {
   try {
      return & Retrieve( key );
   }
   catch(...) {
      return NULL;
   }
}
template<typename Key, typename T, typename comp>
const T* BinarySearchTree<Key, T, comp>::find( const Key& key ) const {
   try {
      return & Retrieve( key );
   }
   catch(...) {
      return NULL;
   }
}
//**********************************
//*		operator[]
//**********************************
template<typename Key, typename T, typename comp>
T& BinarySearchTree<Key, T, comp>::operator[](const Key &index) {
   try {
      return Retrieve( index );
   }
   catch(...) {
      Insert( index, T() );
      return Retrieve( index );
   }
}


#endif
